package cn.xkai.exercise.c;

import com.google.gson.Gson;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @description: 前 K 个高频元素
 * @author: kaixiang
 * @date: 2022-07-28
 **/
public class Solution107 {

    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        LinkedList<int[]> lists = new LinkedList<>();
        for (Map.Entry entry : map.entrySet()) {
            lists.add(new int[]{(int) entry.getKey(), (int) entry.getValue()});
        }
        lists.sort((a, b) -> b[1] - a[1]);
        for (int i = 0; i < k; i++) {
            res[i] = lists.get(i)[0];
        }
        return res;
    }

    public int[] topKFrequentQueue(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : set) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (queue.size() < k) {
                queue.offer(new int[]{key, value});
            } else {
                if (value > queue.peek()[1]) {
                    queue.poll();
                    queue.offer(new int[]{key, value});
                }
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        Solution107 solution107 = new Solution107();
        System.out.println(new Gson().toJson(solution107.topKFrequent(nums, k)));
    }
}
